package advanced.class01;

import basic.untils.ArrayTestUntil;

import java.util.Arrays;

public class Test {

    // ############################----------手撕BFPRT----------###################################
    // --------------------方法一： 堆排（对比BFPRT）---------------------------
    // 获取前k小的数构成数组返回
    public static int[] getMinKNumsByHeap(int[] arr, int k) {
        if(k < 1 || k > arr.length) return null;  // k越界返回null
        int[] minArr = new int[k];
        // 抽取arr的前k个元素构成大顶堆
        for (int i = 0; i < k; i++) {
            heapInsert(minArr,arr[i],i);
        }
        // 然后从arr数组的第k个元素开始
        for (int i = k; i < arr.length; i++) {
            // 如果当前元素小于堆顶，则插入
            if(arr[i] < minArr[0]) {
                minArr[0] = arr[i];
                // 调整数组，重新构造大顶堆
                heapfiy(minArr,0,k);
            }
        }
        return minArr;
    }

    // 调整数组为大顶堆
    private static void heapfiy(int[] minArr, int index, int heapSize) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int largest = index;
        while(left < heapSize){
            if(minArr[index] < minArr[left]){
                largest = left;
            }
            if(right < heapSize && minArr[right] > minArr[largest]){
                largest = right;
            }
            if(largest == index){
                // 没有调整
                break;
            }
            swap(minArr,index,largest);
            // 更新各个指针的位置
            index = largest;
            left = index * 2 + 1;
            right = index * 2 + 2;
        }
    }

    private static void heapInsert(int[] minArr, int value, int index) {
        minArr[index] = value;
        while(index != 0){
            int parent = (index - 1) / 2;
            if(minArr[index] > minArr[parent]){
                swap(minArr,index,parent);
                index = parent;
            }else{
                break;
            }
        }
    }

    private static void swap(int[] arr, int x, int y){
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    // --------------------方法一： BFPRT算法  ---------------------------
    // 获取前k小的数构成数组返回
    public static int[] getMinKNumsByBFPRT(int[] arr, int k) {
        // 首先边界判断
        if(k < 1 || k > arr.length) {
            return arr;
        }
        // 获取当前数组第K小的值
        int minK = getMinKthByBFPRT(arr,k);   // 获取数组中第k小的元素
        // 遍历数组获取前k个元素加入res
        int[] res = new int[k];
        int ca = 0;
        int cr = 0;
        while(cr < res.length && ca < arr.length){
            if(arr[ca] <= minK){
                res[cr++] = arr[ca++];
            }else{
                ca++;
            }
        }
        return res;
    }

    /**
     * 获取数组中第k小的元素
     * @param arr
     * @param k
     * @return
     */
    private static int getMinKthByBFPRT(int[] arr, int k) {
        // 用拷贝的数组进行排序，避免对原始数组造成破坏
        int[] copyArr = copyArray(arr);
        // 用复制的数组求第k小的元素
        // 注意：这里传入参数是K-1,因为要计算第k小的元素其实就是选择排序之后数组中的第k-1位置的元素
        return select(copyArr,0,copyArr.length - 1,k-1);
    }

    /**
     * 主方法
     * @param arr
     * @param begin  排序数组的起始位置
     * @param tail   排序数组的结束位置
     * @param k      寻找排序后的k下标位置的元素
     * @return
     */
    private static int select(int[] arr, int begin, int tail, int k) {
        // 如果当前搜索数组只有一个元素，那么直接返回当前位置的元素
        if(begin == tail) return arr[begin];
        // 实现一个递归调用，计算当前数组的中位数（5个一组，求中位数）
        int pivot = medianOfMedians(arr,begin,tail);
        // 用这个搜索出来pivot进行快排
        int[] border = partition(arr,begin,tail,pivot);
        // 如果要查找的k刚好在边界里面，则直接返回k位置的元素
        if(k >= border[0] && k <= border[1]){
            return arr[k];
        }else if(k < border[0]){
            return select(arr, begin, border[0]-1, k);
        }else{
            return select(arr, border[1] + 1, tail, k);
        }
    }

    /**
     * 快速排序的实现方法
     * @param arr
     * @param begin
     * @param tail
     * @param pivot
     * @return
     */
    private static int[] partition(int[] arr, int begin, int tail, int pivot) {
        // 首先定义数组的两个指针
        int pre = begin - 1;
        int temp = begin;
        int last = tail + 1;
        while(temp < last){
            if(arr[temp] < pivot){
                swap(arr,++pre,temp++);
            }else if(arr[temp] == pivot){
                temp++;
            }else{
                swap(arr,temp,--last);
            }
        }
        return new int[]{pre+1,last-1};
    }

    /**
     * 创建一个函数，计算当前数组中的中位数
     * @param arr
     * @param begin
     * @param tail
     * @return
     */
    private static int medianOfMedians(int[] arr, int begin, int tail) {
        // 计算出当前求解数组的长度
        int len = tail - begin + 1;
        // 将数组分为5个一组
        int offset = len % 5 == 0 ? 0 : 1;
        // 创建数组存储每5个元素的中位数
        int[] curArr = new int[len/5 + offset];
        //  下面就是计算每5个元素的中位数，填入数组
        for (int i = 0; i < curArr.length; i++) {
            int s = begin + i * 5;
            int e = s + 4;
            // 计算中位数
            curArr[i] = getCurMedian(arr,s,Math.min(e,tail));
        }
        // 递归调用select找到当前所见之后的中位数
        return select(curArr,0,curArr.length - 1,curArr.length / 2);
    }

    /**
     * 计算仅有5个元素排序后的中位数
     * @param arr
     * @param start
     * @param end
     * @return
     */
    private static int getCurMedian(int[] arr, int start, int end) {
        // 然后就是插入排序进行排序
        insertSort(arr,start,end);
        // 获取中位数
        int middle = (start + end + 1) / 2;
        return arr[middle];
    }

    /**
     * 实现一个插入排序
     * @param arr
     * @param start
     * @param end
     */
    private static void insertSort(int[] arr, int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            for (int j = i; j > start ; j--) {
                if(arr[j - 1] > arr[j]){
                    swap(arr,j,j-1);
                }else{
                    break;
                }
            }
        }
    }

    /**
     * 拷贝数组
     * @param arr
     * @return
     */
    private static int[] copyArray(int[] arr) {
        int[] copyArr = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            copyArr[i] = arr[i];
        }
        return copyArr;
    }


    //******************      测试         ************************
    public static void main(String[] args) {
        // 生成随机数组，用作测试
        int[] arr = ArrayTestUntil.generateRandomArray(10000,10000);

        long s1 = System.currentTimeMillis();
        int[] res = getMinKNumsByHeap(arr, 20);
        Arrays.sort(res);
        System.out.println(Arrays.toString(res));
        System.out.println("普通归并排序用时：  " + (System.currentTimeMillis() - s1) + "ms");

        long s2 = System.currentTimeMillis();
        int[] res2 = getMinKNumsByBFPRT(arr, 20);
        Arrays.sort(res2);
        System.out.println(Arrays.toString(res2));
        System.out.println("普通归并排序用时：  " + (System.currentTimeMillis() - s1) + "ms");
    }

}
